package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.junit.Test;

public class Q164 {
	/**
	 * @paramn n: An integer
	 * @return: A list of root
	 */
	public List<TreeNode> generateTrees(int n) {
		// write your code here
		boolean[] used = new boolean[n + 1];
		int count = 0;
		Set<String> filter = new HashSet<>();
		TreeNode root = null;
		search(1, count, filter, root, n, used);
		List<TreeNode> rs = new ArrayList<>();
		for (String s : filter) {
			rs.add(decode(s));
		}
		return rs;
	}

	private TreeNode decode(String s) {
		String[] strings = s.split("->");
		TreeNode root = build(0, strings);
		return root;
	}

	private TreeNode build(int i, String[] strings) {
		if (i >= strings.length) {
			return null;
		}
		if ("#".equals(strings[i])) {
			return null;
		}
		TreeNode node = new TreeNode(Integer.parseInt(strings[i]));
		node.left = build(2 * i + 1, strings);
		node.right = build(2 * i + 2, strings);
		return node;
	}

	private void search(int index, int count, Set<String> filter, TreeNode root, int n, boolean[] used) {
		// TODO Auto-generated method stub
		if (count == n) {
			String s = encode(root);
			filter.add(s);
			return;
		}
		for (int i = 1; i <= n; i++) {
			if (!used[i]) {
				used[i] = true;
				count++;
				root = add(root, i);
				search(i, count, filter, root, n, used);
				count--;
				used[i] = false;
				root = remove(root, i);
			}
		}

	}

	private TreeNode remove(TreeNode root, int i) {
		if (root.val < i) {
			root.right = remove(root.right, i);
		} else if (root.val > i) {
			root.left = remove(root.left, i);
		} else {
			return null;
		}
		return root;
	}

	private TreeNode add(TreeNode root, int i) {
		if (root == null) {
			root = new TreeNode(i);
		} else if (root.val < i) {
			root.right = add(root.right, i);
		} else if (root.val > i) {
			root.left = add(root.left, i);
		}
		return root;
	}

	private String encode(TreeNode node) {
		List<TreeNode> list = new ArrayList<>();
		boolean hasItem = true;
		list.add(node);
		StringBuffer sb = new StringBuffer();
		while (!list.isEmpty() && hasItem) {
			hasItem = false;
			List<TreeNode> tmp = new ArrayList<>();
			for (TreeNode t : list) {
				if (t == null) {
					sb.append("#").append("->");
					tmp.add(null);
					tmp.add(null);
				} else {
					sb.append(t.val).append("->");
					tmp.add(t.left);
					tmp.add(t.right);
					if (t.left != null) {
						hasItem = true;
					}
					if (t.right != null) {
						hasItem = true;
					}
				}
			}
			list = tmp;
		}
		return sb.toString();
	}

	@Test
	public void testA() {
		List<TreeNode> rs = generateTrees(3);
		for (TreeNode t : rs) {
			System.out.println(encode(t));
		}
	}

}
